package com.myjianzhu.zzt88.exercise.java.algorithm;

/**
 * Created by jimmytsai on 2016/12/6.
 */

public class AlgorithmExercise {

    static int[] data = new int[]{31, -41, 59, 26, -53, 58, 97, -93, -23, 84};

    public static void main(String[] args) {
        testGetMax();
        test2();
    }


    /**
     * 扫描算法，最优的方法
     */
    static void testGetMax() {
        int maxfar = 0;
        int maxendinghere = 0;
        for (int i = 0; i < data.length; i++) {
            maxendinghere = maxendinghere + data[i] > 0 ? maxendinghere + data[i] : 0;
            maxfar = maxfar > maxendinghere ? maxfar : maxendinghere;
        }
        System.out.println("maxfar:" + maxfar);

    }
//    -------end--------------

    /**
     * 分治算法
     */
    static void test2() {
        int answer = maxsum(0, data.length - 1);
        System.out.println("answer:" + answer);

    }

    static int maxsum(int i, int j) {
        if (i > j) return 0;
        if (i == j) return max(0, data[i]);
        int m = (i + j) / 2;
        int lmax = 0, sum = 0;
        for (int a = m; a >= i; a--) {
            sum += data[a];
            lmax = max(lmax, sum);
        }
        int rmax = 0;
        sum = 0;
        for (int a = m + 1; a <= j; a++) {
            sum += data[a];
            rmax = max(rmax, sum);
        }
        return max(lmax + rmax, maxsum(i, m), max(m + 1, j));
    }

    //    -------end-------------
    private static int max(int i, int j, int k) {
        if (j > i) i = j;
        if (k > i) i = k;
        return i;
    }


    static int max(int a, int b) {
        return a > b ? a : b;
    }
}
